<?php
/**
 * N的阶乘末尾有多个0
 *
 * 阶乘
 * N! = 1*2*3*...N;
 * 比如 5! = 1*2*3*4*5 = 120  末端有1个0
 *
 * 解题思路：
 * N! = K*(10^M)
 * N的阶乘为K和10的M次方的乘积，那么N!末尾就有M的0。如果将N的阶
 * 乘分解后，那么
 * N的阶乘可以分解为： 2的X次方，3的Y次方，4的5次Z方，.....的成绩。由于10 = 2 *
 * 5,所以M只能和X和Z有关，每一对2和5相乘就可以得到一个10，于是M = MIN(
 * X,Z),不难看出X大于Z，因为被2整除的频率比被5整除的频率高的多。所以可以把公式简化为M=Z
 * 所以我们求解N的阶乘最后的0.相当于求解里面有多个5的因子
 *
 * 当我们遇到一大问题可以拆成一个个小的问题，来求解。
 *
 */

function factorial($n)
{
    $n = intval($n);
    if ($n < 0) {
        return 0;
    }
    $sum = 0;
    for ($i = 5; $i <= $n; $i = $i + 5) {
        $j = $i;

        //求解5的个数 比如15 里面有3个5
        while ($j % 5 == 0) {
            $sum++;
            $j = $j / 5;
        }
    }
    return $sum;

}

var_dump(factorial(100));

var_dump(factorial(1));
